// https://leetcode.cn/problems/hanota-lcci/description/

// 算法思路总结：
// 1. 递归解决汉诺塔问题，经典分治算法
// 2. 将n个盘子从A移到C，借助B作为辅助柱
// 3. 递归步骤：先将n-1个从A移到B，将最大的从A移到C，再将n-1个从B移到C
// 4. 基准情况：当只有一个盘子时直接移动
// 5. 通过递归调用实现盘子移动的完整过程
// 6. 时间复杂度：O(2ⁿ)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        int m = A.size();
        dfs(m, A, B, C);    
    }

    void dfs(int m, vector<int>& A, vector<int>& B, vector<int>& C)
    {
        if (m == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return ;
        }
        dfs(m - 1, A, C, B);
        C.push_back(A.back());
        A.pop_back();
        dfs(m - 1, B, A, C);
    }
};

int main()
{
    vector<int> A1 = {2, 1, 0}, B1 = {}, C1 = {};
    vector<int> A2 = {1, 0}, B2 = {}, C2 = {};

    Solution sol;

    sol.hanota(A1, B1, C1);
    sol.hanota(A2, B2, C2);

    for (const int& num : C1)
        cout << num << " ";
    cout << endl;

    for (const int& num : C2)
        cout << num << " ";
    cout << endl;


    return 0;
}